#include <iostream>
#include <cassert>
using namespace std;
template <class T>
class List
{
	struct ListNode // 链表
	{
		T data;
		ListNode* pre;
		ListNode* next;
	};
private:
	ListNode* m_list;
	int m_size;
public:
	List()
	{
		m_list = new ListNode; // 头结点
		m_list->pre = nullptr; // 指向前驱
		m_list->next = nullptr; // 指向后继
		m_size = 0;
	}
	List(const T data) : List() // 委托构造
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->pre = m_list;
		node->next = nullptr;
		m_list->next = node;
		m_size++;
	}
	~List()
	{
		ListNode* pr = nullptr; // pr 为释放指针
		ListNode* it = m_list; // it 为迭代指针
		while (it)
		{
			pr = it;
			it = it->next;
			delete pr;
		}
		m_list = nullptr;
		m_size = -1; // 头结点被删除
	}
public:
	void push_back(T const data)
	{
		ListNode* current = m_list;
		while (current->next != nullptr)
			current = current->next;
		ListNode* node = new ListNode;
		node->data = data;
		node->pre = current;
		node->next = nullptr;
		current->next = node;
		m_size++;
	}
	void pop_back()
	{
		if (empty())
			return;
		ListNode* current = m_list;
		while (current->next != nullptr)
			current = current->next;
		ListNode* pre = current->pre;
		delete current;
		pre->next = nullptr;
		m_size--;
	}
	void push_front(const T data)
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->pre = m_list;
		node->next = m_list->next;
		if (node->next != nullptr) // 空指针没有指向前驱的结点
			node->next->pre = node;
		m_list->next = node;
		m_size++;
	}
	void pop_front()
	{
		if (empty())
			return;
		ListNode* current = m_list->next;
		if (current->next != nullptr) // 空指针没有指向前驱的结点
			current->next->pre = m_list;
		m_list->next = current->next;
		delete current;
		m_size--;
	}
	void insert(const T data, int pos)
	{
		assert(pos < m_size); // 断言替代if
		ListNode* current = m_list->next;
		for (int i = 0; i < pos; ++i)
		{
			current = current->next;
		}
		ListNode* node = new ListNode;
		node->data = data;
		node->pre = current->pre;
		node->next = current;
		current->pre->next = node;
		current->pre = node;
		m_size++;
	}
	void erase(const T data)
	{
		if (empty())
			return;
		ListNode* current = m_list->next;
		while (current != nullptr && current->data != data)
			current = current->next;
		if (current == nullptr)
			return;
		ListNode* pre = current->pre;
		pre->next = current->next;
		if (current->next != nullptr)
			current->next->pre = pre;
		delete current;
		m_size--;
	}
	void clear()
	{
		ListNode* pr = nullptr; // pr 为释放指针
		ListNode* it = m_list->next; // it 为迭代指针
		while (it)
		{
			pr = it;
			it = it->next;
			delete pr;
		}
		m_list->next = nullptr; // 头结点未被删除
		m_size = 0;
	}
public:
	bool empty()
	{
		return !m_list->next;
	}
	int size()
	{
		return m_size;
	}
	int find(const T data)
	{
		ListNode* current = m_list->next;
		for (int i = 0; i < m_size; ++i)
		{
			if (current->data == data)
				return i;
		}
		return -1;
	}
	T& operator[](int const pos)
	{
		assert(pos < m_size);
		ListNode* current = m_list->next;
		for (int i = 0; i < pos; ++i)
			current = current->next;
		return current->data;
	}
};
int main()
{
	List<int> list;
	list.push_back(1);
	list.push_back(2);
	list.push_back(3);
	list.push_back(4);
	list.push_back(5);
	list.push_front(6);
	list.push_front(7);
	list.push_front(8);
	list.push_front(9);
	list.push_front(10);
	list.erase(3);
	list.erase(5);
	list.erase(7);
	list.erase(1);
	list.erase(10);
	list.erase(10);
	list.erase(10);
	list.erase(9);
	list.clear();
	for (int i = 0; i < list.size(); ++i)
		cout << list[i] << " ";
	return 0;
}